#include<iostream>
 struct AvlNode
 {
  Comparable element;
  AvlNode *left;
  AvlNode *right;
  int height;
 
  AvlNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0 )
  : element{ ele }, left{ lt }, right{ rt }, height{ h } { }
  
  AvlNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h = 0 )
  : element{ std::move( ele ) }, left{ lt }, right{ rt }, height{ h } { }
 };

 int height( AvlNode *t ) const
 {
  return t == nullptr ? -1 : t->height;
 }
 
 void insert( const Comparable & x, AvlNode *&t)
 {
  if( t == nullptr )
    t = new AvlNode{ x, nullptr, nullptr };
  else if( x < t->element )
    insert( x, t->left );
  else if( t->element < x )
    insert( x, t->right );

  AvlTree( t );
 }

 static const int ALLOWED_IMBALANCE = 1;
 
 void AvlTree( AvlNode *&t)
 {
  if( t == nullptr )
    return;

  if( height( t->left ) - height( t->right ) > ALLOWED_IMBALANCE )
    if( height( t->left->left ) >= height( t->left->right ) )
       rotateWithLeftChild( t );
    else
       doubleWithLeftChild( t );
  else
    if( height( t->right ) - height( t->left ) > ALLOWED_IMBALANCE )
       if( height( t->right->right ) >= height( t->right->left ) )
          rotateWithRightChild( t );
       else
          doubleWithRightChild( t );
  
  t->height = max( height( t->left ), height( t->right ) ) + 1;
 }
 
 void rotateWithLeftChild( AvlNode * & k2 )
 {
  AvlNode *k1 = k2->left;
  k2->left = k1->right;
  k1->right = k2;
  k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
  k1->height = max( height( k1->left ), k2->height ) + 1;
  k2 = k1;
 }
 
 void doubleWithLeftChild( AvlNode * & k3 )
 {
  rotateWithRightChild( k3->left );
  rotateWithLeftChild( k3 );
 }
 
 void remove( const Comparable & x, AvlNode *&t)
 {
  if( t == nullptr )
     return; 

  if( x < t->element )
     remove( x, t->left );
  else if( t->element < x )
     remove( x, t->right );
  else if( t->left != nullptr && t->right != nullptr ) 
  {
     t->element = findMin( t->right )->element;
     remove( t->element, t->right );
  }
  else
  {
     AvlNode *oldNode = t;
     t = ( t->left != nullptr ) ? t->left : t->right;
     delete oldNode;
  }
 
  AvlTree( t );
 }
 
struct SplayNode
{
  SplayNode *parent; 
  Comparable element; 
  SplayNode *left;
  SplayNode *right;
  int height;
  
  SplayNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0, SplayNode *pa )
  : element{ ele }, left{ lt }, right{ rt }, parent{ pa }, height{ h } { }
  
  SplayNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h = 0,SplayNode *pa )
  : element{ std::move( ele ) }, left{ lt }, right{ rt }, parent{ pa }, height{ h } { }
};

 int height( SplayNode *t ) const
 {
  return t == nullptr ? -1 : t->height;
 }
 
 void SplayTree(SplayNode * & t,SplayNode * & root)
{
    if( t == nullptr )
        return;
	if (root->left==t) 
        rotateWithRightChild( root );
    else if(root->right==t) 
        rotateWithLeftChild( root );
    else if(t->parent->parent->left==t->parent&&t->parent->right=t)
        doubleWithLeftChild( t->parent->parent );
    else if(t->parent->parent->right==t->parent&&t->parent->left=t)
        doubleWithRightChild( t->parent->parent );
    else if(t->parent->parent->left==t->parent&&t->parent->left=t)
        rotateWithLeftChild( t->parent );
        rotateWithLeftChild( t->parent->parent );
    else
        rotateWithRightChild( t->parent );
        rotateWithRightChild( t->parent->parent );
}

void insert2( const Comparable & x, SplayNode *&t)
 {
  if( t == nullptr )
    t = new SplayNode{ x, nullptr, nullptr };
  else if( x < t->element )
    insert2( x, t->left );
  else if( t->element < x )
    insert2( x, t->right );

  SplayTree( t );
 }
 
 void remove2( const Comparable & x, SplayNode *&t)
 {
  if( t == nullptr )
     return; 

  if( x < t->element )
     remove( x, t->left );
  else if( t->element < x )
     remove( x, t->right );
  else if( t->left != nullptr && t->right != nullptr ) 
  {
     t->element = findMin( t->right )->element;
     remove( t->element, t->right );
  }
  else
  {
     SplayNode *oldNode = t;
     t = ( t->left != nullptr ) ? t->left : t->right;
     delete oldNode;
  }
 
  SplayTree( t );
 }
